package org.example.myleet.p969;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> pancakeSort(int[] arr) {
        int n = arr.length;
        if (n < 2 || isAscendSorted(arr, n)) {
            return new ArrayList<>(0);
        }
        List<Integer> result = new ArrayList<>(10 * n);
        for (int i = n; i >= 1; --i) {
            for (int j = 0; j < n; ++j) {
                if (arr[j] == i) {
                    //每当找到i（即当前需要寻找的最大的数，每找到一个，下一次循环减1），就将i通过2次swap放到对应位置i-1上
                    swap(arr, 0, j);
                    result.add(j + 1);
                    swap(arr, 0, i - 1);
                    result.add(i);
                    break;
                }
            }
        }
        //总共需要执行swap次数为2*(n-1)
        return result;
    }

    /**
     * swap array including start and end
     */
    private void swap(int[] arr, int start, int end) {
        int t;
        while (start < end) {
            t = arr[start];
            arr[start] = arr[end];
            arr[end] = t;
            ++start;
            --end;
        }
    }

    private boolean isAscendSorted(int[] arr, int n) {
        for (int i = 1; i < n; ++i) {
            if (arr[i] < arr[i - 1]) {
                return false;
            }
        }
        return true;
    }
}
